1. Field of the Invention
The present invention relates to an image processing method and apparatus for reducing gradation levels of image data through performing an error diffusion process with multiple levels.
2. Related Prior Art
When an image with a multiple-level gradation obtained through a computer or an image input device, for example, is outputted through an image output device such as a printer with fewer gradation levels, the gradation levels of the image data must be reduced. Pseudo halftone representation has been utilized for maintaining the quality of an original image while reducing levels of gradation. Among several methods of the pseudo halftone representation, an error diffusion method capable of producing a high-quality image has been widely used for printers with two levels of output gradation, for example. A multiple-level error diffusion method with quantization levels of three or above has been offered for an image output device capable of representing gradation levels of three or above.
However, the quality of an image is reduced with the multiple-level error diffusion method with fewer quantization levels. For example, when tones of an original image are close to the quantization levels, texture variations are conspicuous and pseudo contours are produced. This is caused by an absence of a random pattern specific to the error diffusion method, which is partly found in an output image. When a tone of original image data is close to a quantization level, the output level is a single quantization level, causing an absence of a random pattern.
In order to effectively prevent image quality reduction due to texture variations, a method is known for superimposing a regular pattern or random noise on image data. However, the method increases errors in every gradation level in the original image data. This sacrifices the best feature of the error diffusion method for producing minimized errors. Consequently the texture of the regular pattern does not match the texture of the error diffusion method. Another problem is, for example, enhanced roughness in an image output.
A method has been proposed for step-by-step error diffusion processing with levels of two to three, then to five as disclosed in Hiroshi Ochi, "High Quality Multiple-level Error Diffusion Method using Gradation Level Processing", Proceeding of Image Electronics Institute, 24, 1, pp.10-17, 1995. However, it takes longer in performing computation required by the step-by-step processing. Another problem is that roughness is greater since four output levels or above may be used for representing a particular gradation level. A compensation process thereof is required, too.
A general principle of the error diffusion method will now be described in detail with reference to Hitoshi Takaie and Mitsuo Yae, "Gradation Conversion Technique of Digital Image Data with C", in Interface, August 1993, pp.158-171. Problems of the multiple-level error diffusion method will be described as well.
With the error diffusion method pseudo halftones are represented by modulating quantization errors into high frequencies to be less perceptible, considering a characteristic of human visual perception. FIG. 11 is a block diagram of an image processing apparatus for implementing the general error diffusion method. The image processing apparatus comprises: a subtracter 111 for subtracting output data of a filter 114 described below from image input data x(i, j); a quantizer (shown as Q) 112 for quantizing output data of the subtracter 111 for outputting as image output data y(i, j); a subtracter 113 for subtracting output data of the subtracter 111 from the image output data y(i, j); and the filter 114 for filtering the output data of the subtracter 113 for outputting to the subtracter 111. In the figure, e(i, j) represents a quantization error produced through quantization at the quantizer 112. Therefore the output data of the subtracter 113 is quantization error e(i, j). Coordinates of two directions intersecting each other are represented by "i" and "j", respectively. The two directions will be referred to as the i direction and the j direction, respectively.
The filter 114 is a sort of linear filter. The transfer function thereof is determined to be G(z.sub.1, Z.sub.2). Z.sub.1 and z.sub.2 are variables in z transformation in the i direction and the j direction, respectively. The overall configuration of the image processing apparatus in FIG. 11 is regarded as a two-dimensional delta-sigma modulation circuit. Therefore expression (1) below is given for the relationship of input and output in the image processing apparatus.
[Expression 1] EQU Y(z.sub.1, z.sub.2)=X(z.sub.1, z.sub.2)+H(z.sub.1, z.sub.2) E(z.sub.1, z.sub.2) (1)
In expression (1), Y(z.sub.1, z.sub.2), X(z.sub.1, z.sub.2) and E(z.sub.1, z.sub.2) are values of z transformation of y(i, j), x(i, j) and e(i, j), respectively. Transfer function H(z.sub.1, z.sub.2) of a filter for modulating quantization error E(z.sub.1, z.sub.2) is given by expression (2) below.
[Expression 2] EQU H(z.sub.1, z.sub.2)=1-G(z.sub.1, z.sub.2) (2)
The transfer function H(z.sub.1, z.sub.2) indicates a high-pass filter of two-dimensional finite impulse response (FIR). The high-pass filter is a filter for modulating quantization errors which determines a modulation characteristic of quantization error E(z.sub.1, z.sub.2) modulated to a higher frequency. In the following description filters indicated with transfer functions H(z.sub.1, z.sub.2) and G(z.sub.1, z.sub.2) are referred to as filter H(z.sub.1, z.sub.2) and filter G(z.sub.1, z.sub.2), respectively.
G(z.sub.1, z.sub.2) is given by expression (3) below.
[Expression 3] EQU G(z.sub.1, z.sub.2)=.SIGMA..SIGMA.G(n1, n2)z.sup.-n1 (3)
The first .SIGMA. in expression (3) indicates a sum when n1 is from -N.sub.1 to M.sub.1. The second .SIGMA. in expression (3) indicates a sum when n2 is from -N.sub.2 to M.sub.2. Each of N.sub.1, M.sub.1, N.sub.2 and M.sub.2 is a positive integer. A filter coefficient is given by g(n1, n2) and a target pixel by n1=0 and n2=0.
Typical filters as examples of g(i, j), the coefficient of G(z.sub.1, z.sub.2) are given by expressions (4) and (5) below. The * in the expressions represents a target pixel where g(0, 0)=0.
[Expression 4] ##EQU1##
[Expression 5] ##EQU2##
FIG. 12 shows a frequency characteristic of error modulation filter H(z.sub.1, z.sub.2) using filter G(z.sub.1, z.sub.2) given by expression (4). FIG. 13 shows a frequency characteristic of error modulation filter H(z.sub.1, z.sub.2) using filter G(z.sub.1, z.sub.2) given by expression (5). A greater absolute value of frequency indicates a higher frequency in FIG. 12 and FIG. 13. Filter G(z.sub.1, z.sub.2) and filter H(z.sub.1, z.sub.2) using filter G(z.sub.1, z.sub.2) given by expression (4) are called filters of Floyd & Steinberg (referred to as Floyd's filter in the following description). Filter G(z.sub.1, z.sub.2) and filter H(z.sub.1, z.sub.2) using filter G(z.sub.1, z.sub.2) given by expression (5) are called filters of Jarvis, Judice & Ninke (referred to as Jarvis' filter in the following description).
FIG. 14 is an image outputted through the error diffusion method with two levels applying a Floyd's filter to an image input of continuous tone. FIG. 15 is an image outputted through the error diffusion method with two levels applying a Jarvis' filter to an image input of continuous tone.
FIG. 12 indicates that gains are low in low frequencies and high in high frequencies for the Floyd's filter. As a result, a fine texture is obtained in the image outputted through the two-level error diffusion method as shown in FIG. 14. FIG. 13 indicates that gains are higher in some degree in low frequencies and low in high frequencies. As a result, a coarse but uniform texture is obtained in the image outputted through the two-level error diffusion method as shown in FIG. 15.
The problem of the multiple-level error diffusion method will now be described with reference to FIG. 16. FIG. 16 is an image outputted through the error diffusion method with five levels applying a Jarvis' filter to an image input of continuous tone as an example of image outputted through the multiple-level error diffusion method. As shown, when gradation levels of an original image are close to the intermediate quantization levels, texture variations are conspicuous and image quality is reduced in the image produced through the multiple-level error diffusion method of the prior art. This is caused by the absence of a random pattern specific to the error diffusion method, which is partly found in the output image. When a tone of the original image data is close to a quantization level, the error is small and the output level is the single quantization level and the result is the absence of the random pattern.
It is an object of the invention to provide an image processing method and apparatus for producing a high-quality image with a uniform texture and reduced roughness through the multiple-level error diffusion method.